/**
 * LinkedStack
 *
 * @author Chris Pratt
 *
 * 1/24/2006
 */
package com.anodyzed.onyx.util;

import java.io.Serializable;
import java.util.ConcurrentModificationException;
import java.util.EmptyStackException;
import java.util.Iterator;
import java.util.NoSuchElementException;

@SuppressWarnings("serial")
public class LinkedStack<E> implements Stack<E>, Serializable {
  /**
   * Node
   */
  private class Node {
    Node up;
    E data;

    /**
     * Constructor
     *
     * @param up The Node One up the Stack
     * @param data The Node Payload
     */
    public Node (Node up,E data) {
      this.up = up;
      this.data = data;
    } //Node

    /**
     * Get the Data from the Node
     *
     * @return The Payload Data
     */
    E get () {
      return data;
    } //get

    /**
     * Get the Next Node up the Stack
     *
     * @return Next Node up the Stack
     */
    Node up () {
      return up;
    } //up

  } //*Node

  /**
   * Itr
   */
  private class Itr implements Iterator<E> {
    private int mod;
    private Node curr,prev;

    /**
     * Constructor
     */
    public Itr () {
      mod = modCount;
      curr = top;
      prev = null;
    } //Itr

    /**
     * Returns <tt>true</tt> if the iteration has more elements. (In other
     * words, returns <tt>true</tt> if <tt>next</tt> would return an element
     * rather than throwing an exception.)
     *
     * @return <tt>true</tt> if the iterator has more elements.
     */
    @Override
    public boolean hasNext () {
      if(mod == modCount) {
        return curr != null;
      }
      throw new ConcurrentModificationException();
    } //hasNext

    /**
     * Returns the next element in the iteration.  Calling this method
     * repeatedly until the {@link #hasNext()} method returns false will
     * return each element in the underlying collection exactly once.
     *
     * @return the next element in the iteration.
     * @exception NoSuchElementException iteration has no more elements.
     */
    @Override
    public E next () {
      if(mod == modCount) {
        if(curr != null) {
          prev = curr;
          curr = curr.up();
          return prev.get();
        }
        throw new NoSuchElementException();
      }
      throw new ConcurrentModificationException();
    } //next

    /**
     * Removes from the underlying collection the last element returned by the
     *  iterator.  This method can be called only once per call to <tt>next</tt>.
     *  The behavior of an iterator is unspecified if  the underlying collection
     *  is modified while the iteration is in progress in any way other than by
     *  calling this method.
     *
     * @exception IllegalStateException if the <tt>next</tt> method has not
     *      yet been called, or the <tt>remove</tt> method has already
     *      been called after the last call to the <tt>next</tt>
     *      method.
     */
    @Override
    public void remove () {
      if(mod == modCount) {
        if(prev != null) {
          Node p = null,n = top;
          while(n != prev) {
            p = n;
            n = n.up();
          }
          if(p == null) {
            top = prev.up();
          } else {
            p.up = prev.up();
          }
        } else {
          throw new IllegalStateException();
        }
      } else {
        throw new ConcurrentModificationException();
      }
    } //remove

  } //*Itr

  private transient int modCount;
  private int size;
  private Node top;

  /**
   * Constructor
   */
  public LinkedStack () {
    modCount = 0;
    size = 0;
    top = null;
  } //LinkedStack

  /**
   * Copy Constructor
   *
   * @param stack The stack to copy
   */
  public LinkedStack (Stack<E> stack) {
    if(!stack.isEmpty()) {
      for(int i = stack.size() - 1;i >= 0;i--) {
        push(stack.peek(i));
      }
    }
  } //LinkedStack

  /**
   * Add an Element to the Top of the Stack
   *
   * @param e The Element to Push onto the Stack
   * @return true if successful
   */
  @Override
  public boolean push (E e) {
    top = new Node(top,e);
    ++size;
    ++modCount;
    return true;
  } //push

  /**
   * Retrieve the Element <code>n</code> from the Top without modifying the
   *  Stack
   *
   * @param n The distance from the top of the stack to peek
   * @return The <code>n</code><small>th</small> Element from the Top of the Stack
   */
  @Override
  public E peek (int n) {
    Node node = top;
    for(int i = 0;i < n;i++) {
      if(node != null) {
        node = node.up();
      } else {
        throw new EmptyStackException();
      }
    }
    if(node != null) {
      return node.get();
    }
    throw new EmptyStackException();
  } //peek

  /**
   * Retrieve the Top Element on the Stack without modifying the Stack
   *
   * @return The Top Element on the Stack
   */
  @Override
  public E peek () {
    if(top != null) {
      return top.get();
    }
    throw new EmptyStackException();
  } //peek

  /**
   * Retrieve and Remove the Top Element from the Stack
   *
   * @return The Top Element on the Stack
   */
  @Override
  public E pop () {
    if(top != null) {
      Node node = top;
      top = node.up();
      --size;
      modCount++;
      return node.get();
    }
    throw new EmptyStackException();
  } //pop

  /**
   * Remove all the Elements from the Stack
   */
  @Override
  public void clear () {
    top = null;
    size = 0;
    modCount++;
  } //clear

  /**
   * Return the number of elements on the Stack
   *
   * @return element count
   */
  @Override
  public int size () {
    return size;
  } //size

  /**
   * Test whether the stack is empty
   *
   * @return true if there are no elements in the stack
   */
  @Override
  public boolean isEmpty () {
    return top == null;
  } //isEmpty

  /**
   * Returns an iterator over a set of elements of type E to walk the stack
   *  from Top to Bottom.
   *
   * @return an Iterator.
   */
  @Override
  public Iterator<E> iterator () {
    return new Itr();
  } //iterator

} //*LinkedStack
